Алгоритм CURE

CURE (англ. Clustering Using Representatives, кластеризация с использованием представителей) является эффективным алгоритмом кластерного анализа для больших баз данных. По сравнению с методом k-средних алгоритм более устойчив к выбросам и способен выявить кластеры, не имеющие сферической формы и с большим разбросом размеров.

Недостатки традиционных алгоритмов

Популярный алгоритм метод k-средних минимизирует сумму квадратов ошибок:

$E=\sum _{i=1}^{k}\sum _{p\in C_{i}}(p-m_{i})^{2},$

Если имеется большая разница в размерах или геометрии различных кластеров, метод квадратичной ошибки может разбить большие кластеры для минимизации квадрата ошибки, что не всегда правильно. Также в случае алгоритмов иерархической кластеризации эта проблема присутствует, так как никакая из мер расстояний между кластерами ($d_{min},d_{mean}$) не стремится работать с различными формами кластеров. Также, время работы большое, если n большое.

Проблема с алгоритмом BIRCH заключается в том, что при генерации кластеров после шага 3 алгоритм использует центр тяжести кластеров и назначает каждую единицу информации кластеру с ближайшим центром тяжести. Использование только центров тяжести для перераспределения точек имеет проблему, если кластеры не образуют однородные размеры и формы.

Алгоритм кластеризации CURE

Чтобы избежать проблем с неоднородными размерами или формами кластеров, CURE использует алгоритм иерархической кластеризации, который принимает компромиссное решение между центром тяжести и всеми крайностями. В алгоритме CURE выбирается постоянная c точек кластера с хорошим распределением и эти точки стягиваются к центру тяжести кластера на некоторое значение. Точки после стягивания используются как представители кластера. Кластеры с ближайшей парой представителей объединяются на каждом шаге алгоритма иерархической кластеризации CURE. Это даёт возможность алгоритму CURE правильно распознавать кластеры и делает его менее чувствительным к выбросам.

Время работы равно O(n² log n), что делает его скорее затратным, а пространственная сложность алгоритма равна O(n).

Алгоритм нельзя применить прямо к большой базе данных ввиду большой сложности вычислений. Следующие улучшения направлены на решение этой проблемы.

• Случайный отбор: Случайный отбор поддерживает большие наборы данных. В общем случае случайный отбор размещается в оперативной памяти. Случайный отбор есть компромисс между точностью и эффективностью.
• Разбиение: Основной идеей является разбиение пространства элементарных событий на p частей. Каждая часть содержит n/p элементов. Первый проход кластеризует каждую часть, пока общее число кластеров не сократится до n/pq для некоторой константы $q\geqslant 1$. Второй проход кластеризации доводит число кластеров до n/q. На втором проходе запоминаются только представляющие точки, поскольку процедура слияния кластеров требует только представителей кластеров перед вычислением представителей объединённого кластера. Разбиение входа сокращает время выполнения.
• Пометка данных на диске: Если даны только представители k кластеров, остальные единицы информации также распределяются по кластерам. Чтобы это сделать, отбирается случайно представляющие точки для каждого из k кластеров и единица информации назначается кластеру, содержащему ближайшего к точке представителя.

Псевдокод

CURE (число точек, k)

Вход : Множество точек S

Выход : k кластеров

• Для каждого кластера u (каждой точки) в u.mean и u.rep запоминается центр тяжести точек кластера и набор из c представителей кластера (начально c = 1, поскольку каждый кластер имеет одну единицу информации). Также в u.closest запоминается ближайший к u кластер.
• Все входные точки вставляются в k-мерное дерево T
• Каждая входная точка трактуется как отдельный кластер, вычисляем u.closest для каждого u, а затем вставляем каждый кластер в кучу Q. (кластеры располагаются в порядке увеличения расстояния от u до u.closest).
• Пока size(Q) > k
• Удаляем верхний элемент кучи Q(u) и объединяем его с его ближайшим кластером u.closest(v), затем вычисляем новых представителей для объединённого кластера w.
• Удаляем u и v из T и Q.
• Для всех кластеров x из Q обновляем x.closest и определяем место x в куче
• вставляем w в Q
• переходим к началу цикла

Доступность

• Библиотека pyclustering с открытым кодом включает реализацию алгоритма CURE на языках Python и C++.

См. также

• Метод k-средних
• Алгоритм BFR

Литература

• Sudipto Guha, Rajeev Rastogi, Kyuseok Shim. CURE: An Efficient Clustering Algorithm for Large Databases // Information Systems. — 1998. — Т. 26, вып. 1. — С. 35–58. — doi:10.1016/S0306-4379(01)00008-4.
• Jacob Kogan, Charles K. Nicholas, Teboulle M. Grouping multidimensional data: recent advances in clustering. — Springer, 2006. — ISBN 978-3-540-28348-5.
• Sergios Theodoridis, Konstantinos Koutroumbas. Pattern recognition. — Academic Press, 2006. — С. 572–574. — ISBN 978-0-12-369531-4.